Variable length codes are well known. Such codes, like the Huffman code, are often used because under certain circumstances, they allow the same amount of information found in fixed length codes to be coded to a fewer number of bits. Although related to Huffman codes, the variable length code generated according to the method and apparatus taught in this disclosure is called a comma code because each code word ends with the same terminating bit, such as a "1". The comma code for the integer m consists of m zeros followed by a "1". Thus, the code word for the data value m=5 would be 00001 (five "0" s followed by the terminating "1"). The total length of the comma code word corresponding to integer m is therefore m+1.
One data compression scheme, called the Rice Algorithm, uses this code extensively and calls it the "Fundamental Sequence." The advantage of using a comma code over a typical Huffman code is the comma code can be easily generated without the use of look up tables.
A prior system for generating a comma code utilizes linear shift registers and control logic. FIG. 1a is a block diagram illustrating the general configuration of such a method. A control circuit 20 is coupled to receive and transmit data from an input buffer 22. The control circuit 20 is also coupled to provide a serial data stream to an m bit serial shift register 24. The shift register 24 can provide a serial or parallel data output.
The control circuit 20 receives an input value m from the input buffer 22. The control circuit 20 then fills the shift register 24 with m zeros followed by a "1". Only then is the control circuit ready strobe in another value.
FIG. 1b provides an example in which the following bit pattern 0110 is input into the serial input of the shift register 24. The bit pattern can be viewed as containing two comma code words, "01" and "1", followed by the start of another code word that begins with a "0". Four clock cycles later the 4 bit pattern fills up the register and can be output as a 4 bit parallel output. An N bit code string requires N clock cycles to generate.
Using a linear shift register to create a comma code has several disadvantages. Besides being slow, the variable rate at which code words are generated makes it difficult to implement in a real time system. If data were input at a constant rate, a system would either have a maximum sized code word assigned and have the system specifically designed to be able to operate upon that sized code word (in order to handle a data stream at a sustained rate) or use a large input buffer to "average-out" the time required for the various code lengths. Designing for the longest code word slows the system down, while including an input buffer adds complexity to a system.